package Meituan;


import com.google.common.collect.Lists;

import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * 最大优惠逻辑中的活动分组
 * @author: leiwenkang02@meituan.com
 * @date: 2018/9/30
 * @time: 11:53
 */
public class GroupActivity {
    /**
     * 1与3互斥
     * 2
     * 3与1互斥
     * 分组结果应该为12，23
     *
     * @param args
     */
    public static void main(String[] args) {
        List<Integer> templateIds = Lists.newArrayList(1, 2, 3);
        Map<Integer, List<Integer>> activityTemplateMap = new HashMap<>();
        activityTemplateMap.put(1, Lists.newArrayList(3));
        activityTemplateMap.put(2, Lists.newArrayList());
        activityTemplateMap.put(3, Lists.newArrayList(1));
        List<List<Integer>> result =  groupActivity(templateIds, activityTemplateMap);
        System.out.println(result);


//        List<List<Integer>> list = Lists.newArrayList(Lists.newArrayList(1,2), Lists.newArrayList(2,3,4)
//                , Lists.newArrayList(1,2,4), Lists.newArrayList(1,2,3));
//
//        List<List<Integer>> result =  removeRedundant(list);
//        System.out.println(result);
    }


    /**
     * 过程解析
     *
     * 顺序遍历1， 2，3
     * 1.先遍历1，把1加到结果里
     * 2.再遍历2，从结果里把已经遍历好的结果全取出来遍历，判断含结果1的list是否有与2不能共存的元素
     * 把能与2共存的元素先放到coExist，如果有元素不能与2共存，表示出现分叉，coExist添加2元素，组成新的结果tempResult
     * 如果某个group中的元素全都可以与2共存，则把2也加到该group中，不会生成新的group。
     *
     *
     */
    public static List<List<Integer>> groupActivity(List<Integer> templateIds, Map<Integer, List<Integer>> activityTemplateMap) {
        List<Integer> coExist = Lists.newArrayList();
        List<List<Integer>> tempActivityGroups = Lists.newArrayList();
        for (int i = 0; i < templateIds.size(); i++) {
            Integer currentTemplateId = templateIds.get(i);
            if (tempActivityGroups.size() == 0) { //第一次遍历，直接加入
                tempActivityGroups.add(Lists.newArrayList(currentTemplateId));
                continue;
            }
            List<List<Integer>> tempResult = Lists.newArrayList();
            for (List<Integer> group : tempActivityGroups) { //遍历所有已分析结果
                boolean biforked = false;
                for (int j = 0; j < group.size(); j++) {
                    if (isCoExist(currentTemplateId, group.get(j), activityTemplateMap)) { //检查当前元素和已存在元素的互斥关系
                        coExist.add(group.get(j)); //可以共存，则加入coExist
                    } else {
                        biforked = true; //标记本组出现分叉
                    }
                }
                if (biforked) { //出现分叉，则结果集中需要新加入一组结果
                    coExist.add(currentTemplateId);
                    tempResult.add(Lists.newArrayList(coExist));
                } else { //新元素和已有元素全部能同享，则直接加入
                    group.add(currentTemplateId);
                }
                //清空标记缓存
                if (coExist.size() != 0) {
                    coExist.clear();
                }
            }
            if (tempResult.size() != 0) {
                tempActivityGroups.addAll(tempResult);
            }
        }
        return removeRedundant(tempActivityGroups);

    }

    private static boolean isCoExist(Integer left, Integer right, Map<Integer, List<Integer>> activityTemplateMap) {
        if (left == null || right == null) {
            return false;
        }
        List<Integer> leftExclusiveIds = activityTemplateMap.get(left);
        if (leftExclusiveIds.size() == 0) {
            return true;
        }
        return !leftExclusiveIds.contains(right);
    }

    /**
     * 有两种情况需要移除
     * 1.包含 如[1,2]，[1,2,3],则需要去除[1,2]
     * 2.等于且已经加入如[1,2]，[1,2]
     */
    private static List<List<Integer>> removeRedundant(List<List<Integer>> activityGroups) {
        if (activityGroups.size() == 0) {
            return Lists.newArrayList();
        }
        List<List<Integer>> acceptGroups = Lists.newArrayList();
        for (int i = 0; i < activityGroups.size(); i++) {
            boolean flag = true;
            List<Integer> currentGroup = activityGroups.get(i);
            for (int j = 0; j < activityGroups.size(); j++) {
                List<Integer> tempGroup = activityGroups.get(j);
                if (tempGroup.size() > currentGroup.size() && tempGroup.containsAll(currentGroup)) { //需要排除
                    flag = false;
                    break;
                }
            }
            for (List<Integer> group : acceptGroups) {
                if (currentGroup.equals(group)) {
                    flag = false;
                }
            }
            if (flag) {
                acceptGroups.add(currentGroup);
            }
        }
        return acceptGroups;
    }

}
